package com.my.code.sort;

import java.util.Arrays;

/**
 * 希尔排序<br>
 * 希尔排序是一种改进后的插入排序，也称为缩小增量排序。
 *
 * @author zzl
 * @date 2020/10/16
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {5, 7, 1, 6, 4, 8, 3, 2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        int len = arr.length;
        int gap = len / 2;
        int tmp;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                tmp = arr[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && arr[preIndex] > tmp) {
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                arr[preIndex + gap] = tmp;
            }
            gap /= 2;
        }
    }

}
